package ext;

import org.junit.Test;

import util.TreeNode;

public class LittleSum {

    private int res = 0;
    int[] tmp;
    public int littleSum(int[] nums) {
        this.tmp = new int[nums.length];
        sort(nums, 0, nums.length - 1);
        return res;
    }

    private void sort(int[] nums, int lo, int hi) {
        if (lo >= hi) {
            return;
        }
        int mid = (hi - lo) / 2 + lo;
        sort(nums, lo, mid);
        sort(nums, mid + 1, hi);
        merge(nums, lo, mid, hi);
    }

    private void merge(int[] nums, int lo, int mid, int hi) {
        int i = lo, j = mid + 1;
        int idx = lo;
        while (i <= mid && j <= hi) {
            if (nums[i] <= nums[j]) {
                //左边比右边小，加上右边比左边多个元素。
                res += (hi - j + 1) * nums[i];
                tmp[idx++] = nums[i++];
            } else {
                tmp[idx++] = nums[j++];
            }
        }
        while (i <= mid) {
            tmp[idx++] = nums[i++];
        }
        while (j <= hi) {
            tmp[idx++] = nums[j++];
        }
        for (i = lo; i <= hi; i++) {
            nums[i] = tmp[i];
        }
    }

    public TreeNode leftestNode(TreeNode root) {
        if (root == null) {
            return null;
        }
        if (root.left == null) {
            return root;
        }
        return leftestNode(root.left);
    }

    @Test
    public void test() {
        int[] nums = new int[]{1,3,4,2,5};
        System.out.println(littleSum(nums));
    }
}
